package com.arron.algorithm.leetcodetop100.动态规划;

import com.arron.algorithm.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 *  打家劫舍一系列套路题解
 *   https://leetcode.cn/problems/house-robber-ii/solutions/67465/tong-yong-si-lu-tuan-mie-da-jia-jie-she-wen-ti-by-/
 */
public class 打家劫舍III {

    //用于记忆化递归储存
    Map<TreeNode,Integer> map = new HashMap<>();

    public int rob(TreeNode root) {


        if (root == null){
            return 0;
        }
        if (map.containsKey(root)){
            return map.get(root);
        }
        //这次直接偷
        int robMoney = root.val ;
        if (root.right != null && root.left == null){
            robMoney =  root.val+rob(root.right.left) +rob(root.right.right);
        }
        if (root.left != null && root.right == null){
            robMoney = root.val+rob(root.left.left)+rob(root.left.right);
        }
        if (root.left!=null && root.right!=null){
            robMoney = root.val+rob(root.left.left)+rob(root.left.right) + rob(root.right.left) +rob(root.right.right);
        }
        //这次不偷
        int notRobMoney = rob(root.left)+rob(root.right);

        //取这次偷，和这次不偷的最大收益
        map.put(root, Math.max(notRobMoney,robMoney));
        return map.get(root);
    }







    public static void main(String[] args) {

        打家劫舍III rob = new 打家劫舍III();


    }

}
